package everydayone.movingCount;

import java.util.LinkedList;

/**
 * @Date 2020/04/08
 * @author 王光浩
 * @Thinking 使用广度优先搜索
 * @Analysis 时间复杂度O（n），空间复杂度O（n）
 */
public class MyMethodOne {
	private LinkedList<int[]> queue=new LinkedList<int[]>();
	public int movingCount(int m, int n, int k) {
		if(k==0)return 1;
		boolean[][] flag=new boolean[m][n];  //用于标记该坐标是否访问过
		queue.add(new int[]{0,0});
		flag[0][0]=true;
		int count=1;
		while(!queue.isEmpty()) {
			int size=queue.size();
			for(int i=0;i<size;i++) {
				int[] index=queue.poll();
				count+=helper(index[0],index[1],flag,k);
			}
		}
		return count;
    }
	/**
	 * 	获取 x,y 的上下左右没有访问且符合要求的元素的个数
	 * @param x
	 * @param y
	 * @param flag
	 * @param k
	 * @return
	 */
	private int helper(int x,int y,boolean[][] flag,int k) {
		int[][] tem= {{1,0},{0,1}};
		int count=0;
		for(int i=0;i<2;i++) {
			int nowX=x+tem[i][0];
			int nowY=y+tem[i][1];
			if(nowX<flag.length && nowY<flag[0].length) {
				if(!flag[nowX][nowY]) {
					flag[nowX][nowY]=true;
					int sum=0;
					//统计nowX和nowY的数位和
					while(nowX>0) {
						sum+=nowX%10;
						nowX/=10;
					}
					while(nowY>0) {
						sum+=nowY%10;
						nowY/=10;
					}
					if(sum<=k) {
						count++;
						queue.add(new int[]{x+tem[i][0],y+tem[i][1]});
					}
				}
			}
		}
		return count;
	}
}
